package 单调递增的数字;

/**
 * createTime: 2025/4/27 10:30
 * description:
 *
 * @author AirMan
 */
public class Solution {
    public int monotoneIncreasingDigits(int n) {
        // 只要发现前面一个数字比后一个数字大，那么我们就将前一个数字减1，并让后面所有的数字改为9
        // 遍历顺序从前往后，那么就会出现当前数字和后一个数字满足达大小关系了，但是又和前一个数字不满足关系了！
        // 所以遍历顺序必须从后向前，始终修改后面的数字为9，这样就保证了向前遍历的时候，当前数字都是比后面小的
        // 局部最优：每次修改的都是低位数字为9（前一个），高位数字（后一个）都是尽量保持不变

        // 使用一个 start 记录从哪一个位置开始，需要将后续的数字修改为9
        char[] nums = (n + "").toCharArray();
        int start = nums.length;
        for (int i = start - 1; i > 0; i--) {
            if (nums[i] < nums[i - 1]) {
                nums[i - 1]--;
                start = i;
            }
        }
        // 重新构建新数字
        for (int i = start; i < nums.length; i++) {
            nums[i] = '9';
        }
        return Integer.parseInt(String.valueOf(nums));
    }
}
